static const int mod_num = 1000000007;

/* 递归函数。 */
int calcNumberFromRecord(int **record, int n, int k)
{
    /* 已有结果的话，可以直接调用。 */
    if(-1 != record[n][k])
    {
        return record[n][k];
    }

    /* 只有一个线段时，两个端点的组合数量就是C(n,2)。 */
    if(1 == k)
    {
        record[n][k] = n * (n - 1) / 2;
        return record[n][k];
    }

    long int result = 0;
    int x = 1, y = 0;

    /* 遍历第一个线段的右边缘。要给k-1个后面的点留足数量，最多只能到下标n-k处。 */
    while(n - k >= x)
    {
        y = calcNumberFromRecord(record, n - x, k - 1);
        result += (long int)y * x;
        x++;
    }

    if(mod_num <= result)
    {
        result %= mod_num;
    }

    record[n][k] = (int)result;
    return record[n][k];
}

int numberOfSets(int n, int k)
{
    int x = 0;
    int record[n + 1][k + 1];
    int *p[n + 1];

    /* 初始化为-1。 */
    memset(record, -1, sizeof(record));

    /* 二维数组不能直接作为入参带入递归函数，需要转换成指针数组，再作为递归函数的入参。 */
    while(n >= x)
    {
        p[x] = &record[x];
        x++;
    }

    x = calcNumberFromRecord(p, n, k);

    return x;
}

